Ông tên thật là Lê Trọng Tố, sinh ngày 1 tháng 10 năm 1914, tại làng Nghĩa lộ, thôn An Định (cũ), xã Yên Nghĩa, huyện Hoài Đức, tỉnh Hà Đông (nay là phường Yên Nghĩa, quận Hà Đông, Hà Nội). Theo cuốn "Họ Trịnh và Thăng Long" (Nhà xuất bản Văn hoá Dân tộc, 2000) của hai nhà nghiên cứu Bỉnh Di và Trịnh Quang Vũ ở trang 111 đã khẳng định đại tướng là hậu duệ của dòng chúa Trịnh Căn.

Cha của ông có biệt danh là cụ Đồ Lê (hay Năng), người đã từng tham gia phong trào Đông Kinh Nghĩa Thục. Khi phong trào bị đàn áp, cụ về làng Thanh Nhàn mở lớp dạy chữ Nho. Năm 1926, cụ Đồ Lê và Nhượng Tống đã tổ chức lễ truy điệu Phan Chu Trinh tại đền Hai Bà Trưng ở làng Đồng Nhân.

Xuất thân từ một gia đình nhà giáo, thời niên thiếu, ông theo học trường Bưởi tại Hà Nội. Vốn học giỏi, lại say mê võ nghệ và bóng đá, ông từng tham gia đội bóng Eclair (Tia chớp) ở vị trí tiền vệ. Do thành tích bóng đá, ông được tuyển vào đội bóng đá của không quân Pháp và nhập ngũ vào lực lượng lính khố đỏ, phục vụ tại đơn vị đồn trú gần sân bay Tông (Sơn Tây)[2]. Do ông từng đeo đến đeo lon đội (tương đương với cấp hàm Hạ sĩ), nên dân làng Yên Nghĩa (gần sân bay Tông, thường gọi ông là Đội Tố. Bà Bích Vân tức Hoàng Ngân khi đó đang phụ trách công tác phụ vận kiêm binh vận của Xứ ủy Bắc Kỳ và một số nhân mối khác được giao nhiệm vụ binh vận Đội Tố và đã thành công. Tham gia Việt Minh từ năm 1944 và là ủy viên quân sự Ủy ban khởi nghĩa của tỉnh Hà Đông từ tháng 8 năm 1945, sau Cách mạng tháng Tám, ông trở thành đảng viên Đảng Cộng sản Đông Dương.